package th.android.sudoku;

import java.awt.*;
import java.util.*;
import java.util.List;

public class ThSudokuGenerator {

    private static final int N = 9;

    public int[][] mFilledSudoKu = new int[N][N];

    private boolean isValid;
    private boolean[][] mRows = new boolean[9][9];
    private boolean[][] mColumns = new boolean[9][9];
    private boolean[][] mBlocks = new boolean[9][9];
    private List<int[]> mBlanks = new ArrayList<>();

    private int randomCount = 0;
    private int[] mLineTags = new int[N];
    private int[] mColumnTags = new int[N];
    private int[] mBoxTags = new int[N];
    public int[][] mGeneratedSudoku = new int[N][N];
    private HashMap<Cell, Integer> mHoles = new HashMap<>();


    public ThSudokuGenerator() {
        autoFill();
    }

    private void autoFill() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (mFilledSudoKu[i][j] == 0) {
                    mBlanks.add(new int[]{i, j});
                } else {
                    int index = mFilledSudoKu[i][j] - 1;
                    mRows[i][index] = mColumns[j][index] = mBlocks[i / 3 * 3 + j / 3][index] = true;
                }
            }

        }
        dfs(0);
    }

    private void dfs(int position) {
        if (position == mBlanks.size()) {
            isValid = true;
            return;
        }
        int[] blank = mBlanks.get(position);
        int i = blank[0], j = blank[1];
        HashSet<Integer> hashSet = new HashSet<>();
        Random random = new Random(System.nanoTime());
        while (hashSet.size() < 9 && !isValid) {
            if (randomCount > 1000) {
                break;
            }
            randomCount++;
            int num = random.nextInt(9);
            if (hashSet.add(num)) {
                int index = i / 3 * 3 + j / 3;
                if (!mRows[i][num] && !mColumns[j][num] && !mBlocks[index][num]) {
                    mRows[i][num] = mColumns[j][num] = mBlocks[index][num] = true;
                    mFilledSudoKu[i][j] = num + 1;
                    dfs(position + 1);
                    mRows[i][num] = mColumns[j][num] = mBlocks[index][num] = false;
                }
            }
        }
    }

    public Sudo easyOne() {
        autoFill();
        for (int i = 0; i < N; i++) {
            System.arraycopy(mFilledSudoKu[i], 0, mGeneratedSudoku[i], 0, N);
        }
        Random random = new Random();
        int holeNum = random.nextInt(7) + 23;
        int count = 0;
        while (mHoles.size() < 23 && count < 10) {
            int max = holeNum - mHoles.size();
            digHole(max, 2);
            removeUnlimitedHole(2);
            count++;
            System.out.println("count = " + count + ", hole`s size = " + mHoles.size());
        }
        return new Sudo(mGeneratedSudoku);
    }

    public Sudo normalOne() {
        autoFill();
        for (int i = 0; i < N; i++) {
            System.arraycopy(mFilledSudoKu[i], 0, mGeneratedSudoku[i], 0, N);
        }
        Random random = new Random();
        int holeNum = random.nextInt(8) + 32;
        int count = 0;
        while (mHoles.size() < 32 && count < 10) {
            int max = holeNum - mHoles.size();
            digHole(max, 3);
            removeUnlimitedHole(3);
            count++;
            System.out.println("count = " + count + ", hole`s size = " + mHoles.size());
        }
        return new Sudo(mGeneratedSudoku);
    }

    public Sudo difficultOne() {
        autoFill();
        for (int i = 0; i < N; i++) {
            System.arraycopy(mFilledSudoKu[i], 0, mGeneratedSudoku[i], 0, N);
        }
        Random random = new Random();
        int holeNum = random.nextInt(5) + 50;
        int count = 0;
        while (mHoles.size() < 50 && count < 100) {
            int max = holeNum - mHoles.size();
            digHole(max, 4);
            removeUnlimitedHole(4);
            count++;
            System.out.println("count = " + count + ", hole`s size = " + mHoles.size());
        }
        check();
        return new Sudo(mGeneratedSudoku);
    }

    public Sudo extremeDifficultOne() {
        autoFill();
        for (int i = 0; i < N; i++) {
            System.arraycopy(mFilledSudoKu[i], 0, mGeneratedSudoku[i], 0, N);
        }
        digHole2(50);
        printArr(mGeneratedSudoku);
        check();
        printArr(mGeneratedSudoku);
        check2();
        return new Sudo(mGeneratedSudoku);
    }

    public Sudo extremeEasyOne() {
        autoFill();
        if (randomCount > 1000) return null;
        randomCount = 0;
        for (int i = 0; i < N; i++) {
            System.arraycopy(mFilledSudoKu[i], 0, mGeneratedSudoku[i], 0, N);
        }
        digHole2(28);
//        printArr(mGeneratedSudoku);
        if (randomCount > 1000) return null;
        check();
        return new Sudo(mGeneratedSudoku);
    }

    private void digHole(int size, int maxFreedom) {
        Random random = new Random();
        for (int num = 0; num < size; num++) {
            int i = random.nextInt(9);
            int j = random.nextInt(9);
            if (mGeneratedSudoku[i][j] == 0) {
                num--;
                continue;
            }
            int index = mFilledSudoKu[i][j] - 1;
            mLineTags[i] |= (1 << index);
            mColumnTags[j] |= (1 << index);
            int boxIndex = i / 3 * 3 + j / 3;
            mBoxTags[boxIndex] |= (1 << index);
            int tag = mLineTags[i] & mColumnTags[j] & mBoxTags[boxIndex];
            int freedom = Integer.bitCount(tag);
            if (freedom < maxFreedom - 2 && freedom > maxFreedom) {
                mLineTags[i] &= (~(1 << index));
                mColumnTags[j] &= (~(1 << index));
                mBoxTags[boxIndex] &= (~(1 << index));
                num--;
            } else {
                mHoles.put(new Cell(i, j), freedom);
                mGeneratedSudoku[i][j] = 0;
            }
        }
    }

    private void digHole2(int size) {
        Random random = new Random();
        for (int num = 0; num < size; num++) {
            if (randomCount > 1000) {
                return;
            }
            randomCount++;
            int i = random.nextInt(9);
            int j = random.nextInt(9);
            if (mGeneratedSudoku[i][j] == 0) {
                num--;
                continue;
            }
            int index = mFilledSudoKu[i][j] - 1;
            mLineTags[i] |= (1 << index);
            mColumnTags[j] |= (1 << index);
            int boxIndex = i / 3 * 3 + j / 3;
            mBoxTags[boxIndex] |= (1 << index);
            int tag = mLineTags[i] & mColumnTags[j] & mBoxTags[boxIndex];
            int freedom = Integer.bitCount(tag);
            mHoles.put(new Cell(i, j), freedom);
            mGeneratedSudoku[i][j] = 0;
        }
    }

    public void removeUnlimitedHole(int limit) {
        Iterator<Map.Entry<Cell, Integer>> iterator = mHoles.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Cell, Integer> entry = iterator.next();
            Cell point = entry.getKey();
            int i = point.x, j = point.y;
            int index = mFilledSudoKu[i][j] - 1;
            int boxIndex = i / 3 * 3 + j / 3;
            int tag = mLineTags[i] & mColumnTags[j] & mBoxTags[boxIndex];
            int freedom = Integer.bitCount(tag);
            if (freedom < 2 || freedom > limit) {
                mLineTags[i] &= (~(1 << index));
                mColumnTags[j] &= (~(1 << index));
                mBoxTags[boxIndex] &= (~(1 << index));
                mGeneratedSudoku[i][j] = mFilledSudoKu[i][j];
                iterator.remove();
            } else {
                entry.setValue(freedom);
            }
        }
    }

    private void check() {
        SudoHelper helper = new SudoHelper();
        List<int[][]> solutions = helper.getTwoSolutions(mGeneratedSudoku);
        int size = solutions.size();
        if (size < 2) return;
        int[][] solutionOne = solutions.get(0);
        int[][] solutionTwo = solutions.get(1);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (solutionOne[i][j] != solutionTwo[i][j]) {
                    mGeneratedSudoku[i][j] = mFilledSudoKu[i][j];
                    clearPos(i, j);
                    break;
                }
            }
        }
        check();
    }

    private void check2() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (mGeneratedSudoku[i][j] != 0) {
                    int index = mGeneratedSudoku[i][j] - 1;
                    mLineTags[i] |= (1 << index);
                    mColumnTags[j] |= (1 << index);
                    int boxIndex = i / 3 * 3 + j / 3;
                    mBoxTags[boxIndex] |= (1 << index);
                    int tag = mLineTags[i] & mColumnTags[j] & mBoxTags[boxIndex];
                    int freedom = Integer.bitCount(tag);
                    mHoles.put(new Cell(i, j), freedom);
                    mGeneratedSudoku[i][j] = 0;
                    SudoHelper helper = new SudoHelper();
                    if (helper.getTwoSolutions(mGeneratedSudoku).size() > 1) {
                        mHoles.remove(new Cell(i, j));
                        mLineTags[i] &= (~(1 << index));
                        mColumnTags[j] &= (~(1 << index));
                        mBoxTags[boxIndex] &= (~(1 << index));
                        mGeneratedSudoku[i][j] = index + 1;
                    }
                }
            }
        }
    }

    private void clearPos(int i, int j) {
        mHoles.remove(new Cell(i, j));
        int index = mFilledSudoKu[i][j] - 1;
        int boxIndex = i / 3 * 3 + j / 3;
        mLineTags[i] &= (~(1 << index));
        mColumnTags[j] &= (~(1 << index));
        mBoxTags[boxIndex] &= (~(1 << index));
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                builder.append(mFilledSudoKu[i][j]);
                if (j != 8) {
                    builder.append(',');
                } else {
                    builder.append('\n');
                }
            }
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        int[] arr = {
                4,6,0,1,5,0,0,0,2,
                0,0,5,7,0,4,0,0,0,
                0,3,0,0,0,0,0,0,0,
                0,9,0,0,6,0,0,0,8,
                0,0,6,0,8,0,5,0,0,
                2,0,0,0,7,0,0,6,0,
                0,0,0,0,0,0,0,1,0,
                0,0,0,9,0,7,4,0,0,
                6,0,0,0,1,3,0,8,9
        };
        int count = 0;
        while (count < 1) {
//            SudokuGenerator generator = new SudokuGenerator();
//            System.out.println(generator);
//            Sudo sudo = generator.extremeDifficultOne();
//            int size = generator.mHoles.size();
//            System.out.println("Holes.size() = " + size);
//            Sudo sudo = new Sudo(arr);
//            System.out.println(sudo);
//            System.out.println(new SudoHelper().printFreedom(sudo.getOriginSudoKu()));
            count++;
        }
        new SudoHelper().getAllSolution(arr);

    }

    public static void printArr(int[][] arr) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                builder.append(arr[i][j]);
                if (j != 8) {
                    builder.append(',');
                } else {
                    builder.append('\n');
                }
            }
        }
        System.out.println(builder.toString());
    }


}
